﻿#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<math.h>

struct ListNode {
	int val;
	struct ListNode* next;
};


//反转链表
//法1：将指针调转指向，倒着指
struct ListNode* reverseList(struct ListNode* head) 
{
	//作图 =>
	//双指针
	//初始，n1（头节点前的空位）指向空，n2（头节点）指向n1
	//但接下来，n2无法再往后走
	// =>
	//三指针
	//n3（第二节点）
	//n2赋给n1，n3赋给n2，之后n2指向n1
	//n2为空时结束上述过程
	if (head == NULL)
		return NULL;
	struct ListNode* n1, * n2, * n3;
	n1 = NULL;
	n2 = head;
	n3 = n2->next;
	while (n2)
	{
		//翻转
		n2->next = n1;
		//迭代
		n1 = n2;
		n2 = n3;
		if (n3)//n3是否为空
		{
			n3 = n3->next;
		}
	}
	return n1;//最终，原链表的尾即当前链表的头
}
//[补]头节点前的空位 -> 哨兵位的头节点
//特点：不存储有效数据

//法2：头插到新链表
struct ListNode* reverseList2(struct ListNode* head)
{
	//作图 =>
	//cur:原链表的指针
	//newhead：新链表的指针
	//next：cur所指原链表节点的下一位
	//将cur头插给newhead，然后更新newhead为cur，cur更新为next
	//cur为空时结束上述过程
	struct ListNode* cur = head, * newhead = NULL;
	while (cur)
	{
		struct ListNode* next = cur->next;
		//头插
		cur->next = newhead;
		newhead = cur;
		cur = next;
	}
	return newhead;
}




//合并两个有序链表
//将两个升序链表合并为一个新的 升序 链表并返回。
//新链表是通过拼接给定的两个链表的所有节点组成的。
//法：依次比较，取小的尾插
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
	//不带哨兵位
	//if (list1 == NULL)
	//	return list2;
	//if (list2 == NULL)
	//	return list1;
	////双指针，分别指向两个链表
	//struct ListNode* cur1 = list1, * cur2 = list2;
	////创建一共新链表，有头，有尾
	//struct ListNode* head = NULL, * tail = NULL;

	//带哨兵位
	struct ListNode* cur1 = list1, * cur2 = list2;
	struct ListNode* guard = NULL, * tail = NULL;
	guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
	tail->next = NULL;

	//尾插新链表
	while (cur1 && cur2)
	{
		if (cur1->val < cur2->val)
		{
			/*if (head == NULL)
			{
				head = tail = cur1;
			}
			else
			{*/
				tail->next = cur1;
				tail = tail->next;
			/*}*/
			cur1 = cur1->next;
		}
		else
		{
			/*if (head == NULL)
			{
				head = tail = cur2;
			}
			else
			{*/
				tail->next = cur2;
				tail = tail->next;
			/*}*/
			cur2 = cur2->next;
		}
	}
	if (cur1)
	{
		tail->next = cur1;
	}
	if (cur2)
	{
		tail->next = cur2;
	}
	//return head;
	struct ListNode* head = guard->next;
	free(guard);
	return head;
}





//链表分割
//现有一链表的头指针 ListNode* pHead，给一定值x，
//编写一段代码将所有小于x的结点排在其余结点之前，
//且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
//法：搞两个链表，小于尾插到一个链表，大于等于尾插到另一个链表，再链接起来
struct ListNode* partition(struct ListNode* pHead, int x)
{
	struct ListNode* gGuard, * gtail, * lGuard, * ltail;
	gGuard = gtail = (struct ListNode*)malloc(sizeof(struct ListNode));
	lGuard = lGuard = (struct ListNode*)malloc(sizeof(struct ListNode));
	gtail->next = ltail->next = NULL;

	struct ListNode* cur = pHead;
	while (cur)
	{
		if (cur->val < x)
		{
			ltail->next = cur;
			ltail = ltail->next;
		}
		else
		{
			gtail->next = cur;
			gtail = gtail->next;
		}
		cur = cur->next;
	}
	ltail->next = gGuard->next;

	gtail->next = NULL;

	pHead = lGuard->next;
	free(gGuard);
	free(lGuard);

	return pHead;
}




//链表的回文结构
//对于一个链表，请设计一个时间复杂度为O(n), 额外空间复杂度为O(1)的算法，
//判断其是否为回文结构。
//给定一个链表的头指针A，请返回一个bool值，
//代表其是否为回文结构。保证链表长度小于等于900。
//法：先找到中间节点，然后从中间节点开始对后半段逆置，最后比较前半段和后半段

//struct ListNode* middleNode(struct ListNode* head) 
//{
//	struct ListNode* slow, * fast;
//	slow = fast = head;
//	while (fast && fast->next)
//	{
//		slow = slow->next;
//		fast = fast->next->next;
//	}
//	return slow;
//}
//struct ListNode* reverseLisT(struct ListNode* head)
//{
//	struct ListNode* cur = head, * newhead = NULL;
//	while (cur)
//	{
//		struct ListNode* next = cur->next;
//		cur->next = newhead;
//		newhead = cur;
//		cur = next;
//	}
//	return newhead;
//}
//bool chkPalindrome(ListNode* head)
//{
//	struct ListNode* mid = middleNode(head);
//	struct ListNode* rhead = reverseLisT(mid);
//	while (head && rhead)
//	{
//		if (head->val!= rhead->val)
//		{
//			return false;
//		}
//		head = head->next;
//		rhead = rhead->next;
//	}
//		
//	return true;
//
//}


//相交链表
//给你两个单链表的头节点 headA 和 headB ，
//请你找出并返回两个单链表相交的起始节点。
//如果两个链表不存在相交节点，返回 null 。
//法：分别求两个链表的长度，让长的先走使两者有差距步，然后同时走，第一个地址相同就是交点
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
{
	struct ListNode* tailA = headA, * tailB = headB;
	int lenA = 1, lenB = 1;
	//求A的长度
	while (tailA->next)
	{
		tailA = tailA->next;
		++lenA;
	}
	//求B的长度
	while (tailB->next)
	{
		tailB = tailB->next;
		++lenB;
	}
	if (tailA != tailB)
		return NULL;
	int gap = abs(lenA - lenB);
	//默认A长B短
	struct ListNode* longList = headA, *shortList = headB;
	if (lenA < lenB)
	{
		longList = headB;
		shortList = headA;
	}
	//长的先走一段距离
	while (gap--)
	{
		longList = longList->next;
	}
	while (longList != shortList)
	{
		longList = longList->next;
		shortList = shortList->next;
	}
	return longList;
}



//环形链表
//给你一个链表的头节点 head ，判断链表中是否有环。
//[ps]因节点无法确定在环中或环外，故无法遍历链表
//法：快慢指针 - “追及问题”
bool hasCycle(struct ListNode* head) 
{
	//慢指针先进环，快指针后进环，
	//追上则在环中。
	struct ListNode* slow, * fast;
	slow = fast = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
		if (slow == fast)
		{
			return true;
		}
	}
	return false;
}

//[补]为什么一定能追上？
//1.为什么slow走1步，fast走2步，题目会相遇？会不会错过？请证明。
//2.为什么slow走1步，fast走n步（n>=3），他们会相遇？会不会错过？请证明。
//（详见笔记）